๊ฐ์ ๋ฉ๋ชจ๋ฆฌ๋ ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ ํฌ๊ธฐ์ ํ๊ณ๋ฅผ ๊ทน๋ณตํ๊ธฐ ์ํด ๋์จ ๊ธฐ์ ์ด๋ค. ๋ฐ๋ผ์, ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ๋ณด๋ค ํฐ ํ๋ก์ธ์ค๋ฅผ ์ํํ๊ธฐ ์ํด ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ค.
๐งท Demanding Paging
ํ์ฌ ํ์ํ(์๊ตฌ๋๋) ํ์ด์ง๋ง ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ฆฌ๋ ๊ฒ์ ๋งํ๋ค.
- ์ ๊ทผ๋์ง ์๋ ํ์ด์ง๋ ์ ๋ ๋ก๋๋์ง ์๋๋ค.
-
swap in์ด ๋ฐ์ํ ๋, pager๊ฐ ์ด๋ค page๊ฐ ์ฌ์ฉ๋ ๊ฒ์ธ์ง๋ฅผ ์ถ์ธกํ์ฌ ๋ก๋ํ๋ค.
- ๋ก๋๋ ํ์ด์ง์ ๊ทธ๋ ์ง ์์ ํ์ด์ง๋ฅผ
valid-invalid bit๋ก ๊ตฌ๋ถํ๋ค.
- ๋ก๋๋ ํ์ด์ง์ ๊ทธ๋ ์ง ์์ ํ์ด์ง๋ฅผ
๐งท Page Fault
์ด๋ CPU๊ฐ ์๊ตฌํ๋ ํ์ด์ง๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ๋ก๋๋์ด ์์ง ์์ ๊ฒฝ์ฐ๋ก, ์์์ ์ธ๊ธํ valid-invalid bit ์ ๊ฐ์ด i ์ธ ๊ฒฝ์ฐ๋ค.
์๋๋ ์ด๋ฅผ ์ฒ๋ฆฌํ๋ ๋ฐฉ๋ฒ์ด๋ค.
- CPU๊ฐ page table์์ ์ฌ์ฉํ ํ์ด์ง์ ์ ๊ทผํ๋ค.
- ๋ฉ๋ชจ๋ฆฌ์ ๋ก๋๋์ง ์์ ์ํ๋ผ๋ฉด, interrupt๋ฅผ ๋ฐ์์ํจ๋ค.
- Disk์์ ํ์ด์ง๋ฅผ ์ฐพ๋๋ค.
- ์ด๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ ค Frameํํ๋ค.
- page table์ ๊ฐฑ์ ํ๊ณ , CPU์๊ฒ ๋ค์ ์ํํ๋ผ๊ณ ๋ช ๋ นํ๋ค.
๐ช Pure Demanding Paging
ํ๋ก์ธ์ค๊ฐ ์ต์ด๋ก ์คํ๋ ๋ ์ด๋ค ํ์ด์ง๊ฐ ํ์ํ์ง ์ ์ ์์ด, ์๋ฌด ํ์ด์ง๋ ์ฌ๋ฆฌ์ง ์๋๋ค.
- ๋ฐ๋ผ์ ํ๋ก๊ทธ๋จ ์คํ๊ณผ ๋์์ Page fault๊ฐ ๋ฐ์ํ๋ค.
- ์ฆ, ์์ํ๊ฒ ํ์ํ ํ์ด์ง๋ง ์ฌ๋ฆฌ๋ ๊ฒ์ Pure Demanding Paging์ด๋ผ๊ณ ํ๋ค.
๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ต๋ํ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ค๋ ์ฅ์ ์ด ์์ง๋ง, ์์๋ถํฐ Page fault๊ฐ ๋ฐ์ํด ์๋๋ฉด์์๋ ๋๋ฆฌ๋ค๋ ๋จ์ ์ด ์๋ค.
๐ช Prepaging
Pure Demanding Paging๊ณผ๋ ๋ฐ๋๋๋ ๊ฐ๋ ์ผ๋ก, ํ๋ก๊ทธ๋จ ์คํ ์ ํ์ํ ๊ฒ์ด๋ผ ํ๋จ๋๋ ํ์ด์ง๋ฅผ ๋ฏธ๋ฆฌ ์ฌ๋ฆฌ๋ ๊ฒ์ด๋ค.
Page fault๊ฐ ๋ฐ์ํ ํ๋ฅ ์ด ์ ์ด ์๋๋ฉด์์๋ ๋น ๋ฅด์ง๋ง, ๋ฏธ๋ฆฌ ์ฌ๋ผ๊ฐ ํ์ด์ง๋ฅผ ์ฌ์ฉํ์ง ์๋๋ค๋ฉด ๋ฉ๋ชจ๋ฆฌ๊ฐ ๋ญ๋น๋๋ค.
๐ช Swapping vs. Demanding Paging
๋ ๋ค ๋ฉ๋ชจ๋ฆฌ์ backing store ์ฌ์ด๋ฅผ ์ค๊ณ ๊ฐ๋ ๊ธฐ๋ฅ์ ์ํํ์ง๋ง, Swapping์ ํ๋ก์ธ์ค ๋จ์๋ก ์ด๋ํ๊ณ , Demanding Paging์ ํ์ด์ง ๋จ์๋ก ์ด๋ํ๋ค๋ ์ฐจ์ด๊ฐ ์๋ค.
๐งท Page Replacement
Demanding Paging์ ์๊ตฌ๋๋ ํ์ด์ง๋ง backing store์์ ๊ฐ์ ธ์จ๋ค. ํ์ง๋ง ํ๋ก๊ทธ๋จ๋ค์ด ๊ณ์ ์คํ๋๋ฉด์, ์๊ตฌ๋๋ ํ์ด์ง๋ ๋์ด๋๊ณ ๋ฉ๋ชจ๋ฆฌ๋ ์ ํํ๊ธฐ์ ์ธ์ ๊ฐ๋ ๊ฐ๋ ์ฐจ๊ฒ ๋์ด ๋ ์ด์ ์๋ก์ด ํ์ด์ง๋ฅผ ๋ด์ ์ ์๊ฒ ๋ ๊ฒ์ด๋ค.
- ๊ทธ๋ ๋ค๋ฉด, ์ด๋ฏธ ์๋ ํ์ด์ง ์ค ํ๋๋ฅผ ๋ค์ backing store๋ก ๋ด๋ณด๋ด๊ณ , ์๋ก์ด ํ์ด์ง๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ ค์ผ ํ๋๋ฐ, ์ด๋ฅผ Page Replacement๋ผ ํ๋ค.
- backing store๋ก ๋ด๋ณด๋ด๋ ๊ฒ์ page-out, ๊ทธ ๋ฐ๋๋ฅผ page-in์ด๋ผ ํ๋ค.
- ๊ทธ๋ฆฌ๊ณ page-out๋ ํ์ด์ง๋ฅผ victim page๋ผ ํ๋ค.
๐ช Victim Page
ํฌ์์ ํ์ด์ง๋ ์ด๋ค ํ์ด์ง๋ก ์ ํํ๋ ๊ฒ์ด ์ข์๊น.
์ด๋ฏธ ๋ก๋๋ ํ์ด์ง ์ค CPU์ ์์ (modify)๋์ง ์์ ํ์ด์ง๋ฅผ ๊ณ ๋ฅด๋ ๊ฒ์ด ํจ์จ์ ์ด๋ค. ์ด๋ ๊ณง ์ฝ๊ธฐ๋ง ํ๋ ํ์ด์ง๋ฅผ ์๋ฏธํ๋ค. ์ด๋ฌํ ํ์ด์ง๋ page-out์ด ๋ ๋ backing store์ ์ฐ๊ธฐ ์ฐ์ฐ์ ํ ํ์๊ฐ ์๊ธฐ ๋๋ฌธ์ด๋ค.
๊ทธ๋ ๋ค๋ฉด, ํด๋น ํ์ด์ง๊ฐ ์์ ๋์๋์ง ์๋์๋์ง๋ฅผ ๊ตฌ๋ถํ ์ ๋ณด๊ฐ ํ์ํ๋ฐ, ์ด๋ modify bit = dirty bit ๋ฅผ ์ฌ์ฉํ๋ค.
์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์์ ๋์ง ์์ ํ์ด์ง๋ฅผ ๋ํ๋ด๊ณ ์ด ์ค ์ ํํ๋ค.
- ์ด๋, ์ฌ๋ฌ ๊ฐ์ ์์ ๋์ง ์์ ํ์ด์ง๊ฐ ์๋ค๋ฉด ์ด๋ค ํ์ด์ง๋ฅผ ๊ณจ๋ผ์ผ ํ ๊น
๐ช Page Replacement - FIFO
๊ฐ์ฅ ๋จผ์ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ผ์จ, ์์ ๋์ง ์์ ํ์ด์ง๋ฅผ ํฌ์์ ํ์ด์ง๋ก ์ ํํ๋ ๋ฐฉ์์ด๋ค.
- ์ต์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์๋์ง๋ง, ์ ํ์ฑ์๋ ์ํฅ์ ๋ฏธ์น์ง ์๋๋ค.
- ์ด์ ์ page-outํ ํ์ด์ง๋ฅผ ๊ทธ ๋ค์ ๋ฐ๋ก page-inํ๋ ค ํ๋ค๋ฉด ๋ค์ page fault๊ฐ ๋ฐ์ํด ๋นํจ์จ์ ์ด๋ค.
Belady's Anomaly
- ํ๋ ์ ์๊ฐ ์ฆ๊ฐํ๋ฉด(= ๋ฉ๋ชจ๋ฆฌ ์ฉ๋์ด ์ฆ๊ฐํ๋ฉด) page fault ์๊ฐ ์ค์ด๋๋ ๊ฒ์ด ์ด์์ ์ด๋ค.


- ํ์ง๋ง FIFO๋ฅผ ์ฌ์ฉํ๋ฉด, ์์ ๊ฐ์ด ํน์ ์ง์ ์์ ํ๋ ์ ์๊ฐ ์ฆ๊ฐํด๋, page fault ์๊ฐ ์คํ๋ ค ์ฆ๊ฐํ๋ ์ด์ ํ์์ด ๋ฐ์ํ๋ค. ์ด๋ฅผ Belady's Anomaly๋ผ ํ๋ค.
๐ช Page Replacement - Optimal
๋ง๊ทธ๋๋ก, ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ๊ฐ์ฅ ์ค๋ซ๋์ ์ฌ์ฉ๋์ง ์์ ํ์ด์ง๋ฅผ ์ ํํ๋ ๋ฐฉ์์ด๋ค.
- ๋ฏธ๋ฆฌ ๋ฏธ๋ ์ ๋ณด๋ฅผ ์๋ค๋ ๊ฐ์ ํ์, ์ค๋ซ๋์ ์ฌ์ฉํ์ง ์๋ Page๋ฅผ ์ ํํ์ฌ outํ๋ค.
- ์ด๋ก ์ ์ผ๋ก๋ Page fault ๋ฐ์์ ์ค์ผ ์ ์์ง๋ง, ํ์ค์ ์ผ๋ก ๊ตฌํ์ด ๋ถ๊ฐ๋ฅํ๋ค.
๐ช Page Replacement - LRU
Least Recently Used์ ์ฝ์๋ก, ์ต๊ทผ์ ์ฌ์ฉ๋์ง ์์ผ๋ฉด ๋์ค์๋ ์ฌ์ฉ๋์ง ์์ ๊ฒ์ด๋ผ๋ ๊ฐ๋ ์ ์ฌ์ฉํ๋ ๋ฐฉ์์ด๋ค.
- ๊ฐ์ฅ ์ค๋ซ๋์ ์ฌ์ฉํ์ง ์์ ํ์ด์ง๋ฅผ ํฌ์์ ํ์ด์ง๋ก ์ ํํ๋ค.
- OPT๋ณด๋ค๋ Page fault๊ฐ ๋ง์ด ๋ฐ์ํ์ง๋ง, FIFO๋ณด๋ค๋ ์ ๊ฒ ์ผ์ด๋๋ค.
- ๋ง์ ์ด์์ฒด์ ๊ฐ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๐ช Page Replacement - LFU
Least Frequently Used์ ์ฝ์๋ก, ์ฐธ์กฐํ์๊ฐ ๊ฐ์ฅ ์ ์ ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ๊ต์ฒด ๋์์ด ์ฌ๋ฌ ๊ฐ๋ผ๋ฉด ๊ฐ์ฅ ์ค๋ซ๋์ ์ฌ์ฉํ์ง ์์ ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ค.
- ํ์ง๋ง ์ฐธ์กฐ๋ ๊ฐ๋ฅ์ฑ์ด ๋ง์์๋ ๋ถ๊ตฌํ๊ณ , ํ์์ ์์กดํ๊ธฐ์ ์ต๊ทผ์ ์ฌ์ฉ๋ ํ๋ก๊ทธ๋จ์ ๊ต์ฒด์ํฌ ๊ฐ๋ฅ์ฑ์ด ์๋ค.
๐ช Page Replacement - MFU
Most Frequently Used์ ์ฝ์๋ก, LFU์ ๋ฐ๋๋ก ์ฐธ์กฐ ํ์๊ฐ ๊ฐ์ฅ ๋ง์ ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๐งท Thrashing
๋ฉ๋ชจ๋ฆฌ ์์ญ์ ์ ๊ทผํ๊ฒ ๋ ๋, ๋ฉ๋ชจ๋ฆฌ์ Page fault์จ์ด ๋์ ๊ฒ์ ์๋ฏธํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๋ ์ฑ๋ฅ ์ ํ์ ์์ธ์ด ๋๋ค.
๐ช Page-Fault Frequency
๋์ PFF๋ ํ๋ก์ธ์ค์ ํ๋ ์ ์๊ฐ ์ถฉ๋ถํ ๋ง์ง ์์ ๊ฒฝ์ฐ์ ๋ฐ์ํ๊ณ , ๋ฎ์ PFF๋ ํ๋ก์ธ์ค์ ํ๋ ์ ์๊ฐ ๋๋ฌด ๋ง์ ๊ฒฝ์ฐ์ ๋ฐ์ํ๋ค.
- ํ๋ ์ ์๋ฅผ ๊ด๋ฆฌํจ์ผ๋ก์จ PFF๋ฅผ ์กฐ์ ํ ์ ์๋ค.